package Sequence;

public class Test1049 {
    public static void main(String[] args) {
        new Solution1049_1().lastStoneWeightII(new int[]{1,2});
    }
}

class Solution1049_1 {
    public int lastStoneWeightII(int[] stones) {
        int sum = 0;
        for (int stone : stones) sum+=stone;

        int target = sum >> 1;
        int ans = (sum&1)==1 ? 1 : 0;

        boolean[] dp1 = new boolean[target+1];
        boolean[] dp2 = new boolean[target+1];
        dp1[0] = true;

        for (int stone : stones) {
            for (int j = 0; j <= target; j++) {
                if (dp1[j]){
                    dp2[j] = true;
                    if (j+stone<=target) dp2[j+stone] = true;
                }
            }
            boolean[] temp = dp1;
            dp1 = dp2;
            dp2 = temp;
        }

        int max = 0;
        for (int i = target; i > 0; i--) {
            if (dp1[i]){
                max=i;
                break;
            }
        }

        return ans+(target-max)*2;
    }
}
